Bubble Sort Algorithm

An intuitive but inefficient sorting algorithm in order O(n²) steps and using O(1) space.

Compare the first two values (position 1 + 2). Put the smaller in the first place. Now compare the next two values (2 + 3). Put the smaller in the first place. Continue until the you reach the end of the list. The list might not yet be sorted, so start over from the beginning to continue moving the new largest number over to the next-right-most position.

The steps are in order O(n²). After the first loop, the largest element is guaranteed to be positioned last in the array. After the second loop, the second largest is second last. to have every number in the array sorted to their correct position, at worst, it needs n loops. In every loop, it does n-1 comparisons. In total, there are n*(n-1) or n²-n steps. When n is very large, -n factor is insignificant. Thus, n²-n is referred to in the order of n², notated as O(n²) because the algorithm takes about n² steps to complete.

Bubble Sort does not take extra space, so it is in order of O(1) space. Regardless of how big input is, the amount of extra space required is constant.

Bubble Sort can be optimized, but the running time is still in order O(n²). You don't need to do n-1 comparisons every time. After the first for loop, only n-2 comparisons are needed, since the largest element is already known. The steps become (n-1)+(n-2)+...+1 = n*n(n-1)/2, which is two times smaller than before but still in order of O(n²).

(DEV285x)

Pseudocode

* repeat until no swaps
* * for i from 0 to n-2
* * * if i'th and i+[1](/view/1)'th [element](/view/Element)s are [o](/view/O)ut [o](/view/O)f [o](/view/O)rder
* * * * swap them

Code

* static void bubbleSort(int[] [1](/view/1)st) {
* * int n = [1](/view/1)st.length;
* * boolean swapped;
* * do 
* * {
* * * swapped = false;
* * * for (int i = 0; i < n-[1](/view/1); i++) {
* * * * if ([1](/view/1)st[i] > [1](/view/1)st[i+[1](/view/1)]) {
* * * * * int temp  = [1](/view/1)st[i];
* * * * * [1](/view/1)st[i+[1](/view/1)] = temp;
* * * * * swapped = true;
* * * * }
* * * }
* * } while (swapped == true)
* * System.[o](/view/O)ut.println(Arrays.toString([1](/view/1)st));
* }

(DEV285x)